float4x4 World;
float4x4 View;
float4x4 Projection;
float3 cameraPosition;

Texture octree;
sampler octreeSampler : register(s1)  = sampler_state { texture = <octree> ; magfilter = Point; minfilter = Point; mipfilter=Point; AddressU = clamp; AddressV = clamp;};

Texture rays;
sampler raySampler : register(s2)  = sampler_state { texture = <rays> ; magfilter = Point; minfilter = Point; mipfilter=Point; AddressU = clamp; AddressV = clamp;};

int octreeWidth;
int octreeHeight;
int screenWidth;
int screenHeight;

struct NodeDist {
	float dist;
	int node;
};

//For the simulation of the stack, we need
	// Global depth level, ie how many levels are on the stack
	// Ray direction/position
// And per level:
	// Local vars of current recursive function
		// Array of 8 sorted nodes, distance + pointer to node
		// Current index of node we are testing
	// Parameters of called recursive function
		// Pointer to current node

//Octree node = 8 pointers to other nodes, 3 color (RGB), 2x3 floats min/max of node
//So 0-7 pointers, 8-10 colors, 11-13 min, 14-16 max

float4x4 MatrixTransform;

void SpriteVertexShader(inout float4 color    : COLOR0,
                        inout float2 texCoord : TEXCOORD0,
                        inout float4 position : SV_Position)
{
    position = mul(position, MatrixTransform);
}

int mod(int num, int div) {
	return num - ((num / div) * div);
}

bool rayCollidesWithAABB(float4 rayPosition, float4 rayDirection, float3 bl, float3 tr) {
	//TODO: http://gamedev.stackexchange.com/questions/18436/most-efficient-aabb-vs-ray-collision-algorithms

	float3 dirfrac;
	dirfrac.x = 1.0f / rayDirection.x;
	dirfrac.y = 1.0f / rayDirection.y;
	dirfrac.z = 1.0f / rayDirection.z;

	float t1 = (bl.x - rayPosition.x)*dirfrac.x;
	float t2 = (tr.x - rayPosition.x)*dirfrac.x;
	float t3 = (bl.y - rayPosition.y)*dirfrac.y;
	float t4 = (tr.y - rayPosition.y)*dirfrac.y;
	float t5 = (bl.z - rayPosition.z)*dirfrac.z;
	float t6 = (tr.z - rayPosition.z)*dirfrac.z;

	float tmin = max(max(min(t1, t2), min(t3, t4)), min(t5, t6));
	float tmax = min(min(max(t1, t2), max(t3, t4)), max(t5, t6));

	// if tmax < 0, ray (line) is intersecting AABB, but whole AABB is behing us
	if (tmax < 0)
	{
		return false;
	}

	// if tmin > tmax, ray doesn't intersect AABB
	if (tmin > tmax)
	{
		return false;
	}
	return true;
}

float getValAtPos(int pos) {
	float w = (float)mod(pos, octreeWidth) / (float) octreeWidth;
	float h = (float)(pos / octreeWidth) / (float) octreeHeight;
	float2 texcoords = float2(w,h);
	return tex2D(octreeSampler, texcoords).r;
}

float4 queryOctreeNodeAtPos(int pos, float4 rayPosition, float4 rayDirection) {
	/*
	* If the AABB of this node does not intersect the ray, return null
	* Else if this node is a leaf, return the color of this node
	* Else 
		* query all child nodes, in order closest to the camera to furthest, 
		* return any result found, or null is none of the child nodes are filled + intersect the ray
	*/
	//Read top left/bottom right
	float3 bl;
	float3 tr;
	bl.x = getValAtPos(pos + 11);
	bl.y = getValAtPos(pos + 12);
	bl.z = getValAtPos(pos + 13);
	tr.x = getValAtPos(pos + 14);
	tr.y = getValAtPos(pos + 15);
	tr.z = getValAtPos(pos + 16);
	if (!rayCollidesWithAABB(rayPosition, rayDirection, bl, tr)) {
		return float4(0,0,0,0);
	}
	else if (getValAtPos(pos + 8) != 0 || getValAtPos(pos + 9) != 0 || getValAtPos(pos + 10) != 0) {
		return float4(getValAtPos(pos + 8),getValAtPos(pos + 9),getValAtPos(pos + 10),1);
	}
	else {
		// query all child nodes, in order closest to the camera to furthest
		NodeDist ndists[8];
		for (int i = 0; i < 8; i++) {
			if ((int)getValAtPos(pos + i) != 0) {
				ndists[i].node = (int)getValAtPos(pos + i);
				float3 nCenter;
				nCenter.x = (getValAtPos(ndists[i].node + 11) + getValAtPos(ndists[i].node + 14)) / 2;
				nCenter.y = (getValAtPos(ndists[i].node + 12) + getValAtPos(ndists[i].node + 15)) / 2;
				nCenter.z = (getValAtPos(ndists[i].node + 13) + getValAtPos(ndists[i].node + 16)) / 2;
				ndists[i].dist = distance(cameraPosition, nCenter);
			}
		}

		NodeDist sorted[8];
		float currLowest = 10000000.0f;
		for (int j = 0 ; j < 8; j++) {
			currLowest = 10000000.0f;
			for (i = 0; i < 8; i++) {
				//Find lowest value
				if (ndists[i].dist < currLowest) {
					currLowest = ndists[i].dist;
				}
			}
			//Find matching ndists to lowest value
			for (i = 0; i < 8; i++) {
				//Find lowest value
				if (ndists[i].dist == currLowest) {
					sorted[j] = ndists[i];
					ndists[i].dist = 10000000.0f;
					break;
				}
			}
		}
		float4 color = float4(0,0,0,0);
		for (i = 0; i < 8; i++) {
			if (sorted[i].node > 0) {
				color = queryOctreeNodeAtPos(sorted[i].node, rayPosition, rayDirection);
				
				//Test if color, then return
				if (color.r != 0 || color.b != 0 || color.g != 0)
					return color;
			}
		}
	}

	return float4(0,0,0,0);
}

float4 main(float2 texCoord: TEXCOORD0) : COLOR0
{
    float4 tex = float4(getValAtPos(8), getValAtPos(9), getValAtPos(10), 1);

	/*
	* Raycasting algorithm in pseudocode
	* For every pixel on the screen
		* Find the ray from the camera of that pixel
		* For every ray found
			* Query the root of the octree for the closest intersecting voxel that is a leaf
	
	* Querying an octree node:
	* If the AABB of this node does not intersect the ray, return null
	* Else if this node is a leaf, return the color of this node
	* Else 
		* query all child nodes, in order closest to the camera to furthest, 
		* return any result found, or null is none of the child nodes are filled + intersect the ray

	*/

	//Retrieve Ray
	//TODO: Fix texture "alignment"
	//Array goes from 0-X, texture from 0-1.0?
	//Also, try using 2x texture? 
	float4 raypos = tex2D(raySampler, texCoord + float2(-0.0001f*(screenWidth*2.00002f), 0));
	float4 raydir = tex2D(raySampler, texCoord + float2(1.0f/(screenWidth*2.00002f), 0));
	
	/*
	// For ray visualization
	raydir.a = 1.0f;
	raypos.a = 1.0f;
	*/

	//Query octree for the closest intersecting voxel that is a leaf
	float4 result = queryOctreeNodeAtPos(0, raypos, raydir);

    return result;
}


technique Desaturate
{
    pass Pass1
    {
        PixelShader = compile ps_3_0 main();
		VertexShader = compile vs_3_0 SpriteVertexShader();
    }
}
